package com.algorithm.thePrimaryAlgorithm;


import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

class ListNode25 {
    int val;
    ListNode25 next;

    ListNode25() {
    }

    ListNode25(int val) {
        this.val = val;
    }

    ListNode25(int val, ListNode25 next) {
        this.val = val;
        this.next = next;
    }
}

/**
 * 25 回文链表
 */
@Slf4j
public class LinkSulotionLC25 {
    /**
     * 使用 map 的方式 找到中心点 然后双指针 left 从前往后  right 从后往前 比较结点
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode25 head) {
        int lenght = 0;
        ListNode25 tmp = head;
        Map<Integer, ListNode25> map = new HashMap<>();
        while (tmp != null) {
            map.put(lenght, tmp);
            lenght++;
            tmp = tmp.next;
        }
        int hl = lenght / 2;

        int k = lenght - 1;
        for (int i = 0; i < hl; i++) {
            if (i < k && map.get(i).val != map.get(k).val) {
                return false;
            }
            k -= 1;
        }

        return true;
    }

    @Test
    public void test() {
        ListNode25 l1 = getListNode25();
        isPalindrome(l1);

    }

    /**
     * 1 快慢指针 找到中心结点
     * 2 翻转后半段链表
     * 3 比较
     *
     * @param head
     * @return
     */
    public boolean isPalindrome1(ListNode25 head) {
        // 快慢指针 找出链表的中间结点
        ListNode25 slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 如果fast为 null 则链表长度为 偶数
        if (fast != null) {
            slow = slow.next;
        }
        // 翻转 slow
        ListNode25 reverse = null;
        while (slow != null) {
            ListNode25 tmp = slow.next;
            slow.next = reverse;
            reverse = slow;
            slow = tmp;
        }
        // 比较
        while (reverse != null) {
            if (reverse.val != head.val) {
                return false;
            }
            reverse = reverse.next;
            head = head.next;
        }

        return true;
    }

    @Test
    public void test1() {
        ListNode25 l1 = getListNode25();

        isPalindrome1(l1);
    }

    private ListNode25 getListNode25() {
        ListNode25 l1 = new ListNode25(1);
        ListNode25 l2 = new ListNode25(2);
        ListNode25 l3 = new ListNode25(3);
        ListNode25 l4 = new ListNode25(4);
        ListNode25 l5 = new ListNode25(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        return l1;
    }
}
